#ifndef LINKED_LIST_H
#define LINKED_LIST_H

#include "..\\..\\Includes\\Main.h"

using namespace std;

template<typename Type>
class LinkedList
{
public:

     LinkedList();
     void append( Type tData );
     void add_as_first( Type tData );
     void addafter( int nIndex, Type tData );
     void del( Type tData );
     void display();
     int count();
	 Type get( int nIndex );
     ~LinkedList();


private:
     struct node
     {
        Type data;
        node *nextNode;
     }*m_pFirstNode;
};




//------------------------------------------------------------------------------------------


//ALL OF THIS CODE MUST BE IN THE HEADER.
//Totally lame. It won't compile unless I have a forward
//declaration WITH THE TYPENAME in a .cpp file.  That is 
//so weak.

template<typename Type> 
LinkedList<Type>::LinkedList()
{
	m_pFirstNode=NULL;
}


template<typename Type> 
void LinkedList<Type>::append(Type tData)
{
   node *previousNote,*newNode;

   //if our list is empty, add it as the first
   if( m_pFirstNode == NULL )
   {
      m_pFirstNode = new node;
      m_pFirstNode->data = tData;
      m_pFirstNode->nextNode = NULL; //the pointer to the next data will be null
   }
   else
   {
      previousNote = m_pFirstNode;
	  //iterate through until we are at the very end.
      while( previousNote->nextNode != NULL )
        previousNote = previousNote->nextNode;

	  //assign our new node (appended at the end) the data passed in through the function
      newNode = new node;
      newNode->data = tData;
      newNode->nextNode = NULL;
	  //point to the new node added at the end
      previousNote->nextNode = newNode;
   }
}

template<typename Type>
void LinkedList<Type>::add_as_first(Type tData)
{
   node *frontNode;

   frontNode = new node;
   frontNode->data = tData;
   frontNode->nextNode = m_pFirstNode;
   //our first node is the node just added
   m_pFirstNode = frontNode;
}

template<typename Type>
void LinkedList<Type>::addafter( int index, Type tData)
{
   node *iteratingNode, *newNode;
   iteratingNode = m_pFirstNode;

   for(int iter = 0; iter < index; iter++)
   {
	  //iterating node becomes the next one in the list
      iteratingNode = iteratingNode->nextNode;
	  //if it's null, we are at the end of the list... oops
      if( iteratingNode == NULL )
      {
			MikeUtils::ASSERT(false, "Trying to add a node at an index that does not exist!", __FILE__, __LINE__);
			return;
      }
   }

   //so our iteratingNode is now where our new data will go
   newNode = new node;
   newNode->data = tData;
   //the new node is now pointing to the next node
   newNode->nextNode = iteratingNode->nextNode;
   //the iterating node slides in behind the new node
   iteratingNode->nextNode = newNode;
}

template<typename Type>
void LinkedList<Type>::del( Type tData )
{
   node *node1, *node2;
   node1 = m_pFirstNode;
   //wow if you're deleting the first node, it is easy :)
   if( node1->data == tData )
   {
      m_pFirstNode = node1->nextNode;
      delete node1;
      return;
   }

   node2 = node1;
   while( node1!=NULL )
   {
      if( node1->data == tData )
      {
         node2->nextNode = node1->nextNode;
         delete node1;
         return;
      }

      node2 = node1;
      node1 = node1->nextNode;
   }
  // cout<<"\nElement "<<tData<<" not Found.";
}

template<typename Type>
void LinkedList<Type>::display()
{
 //  node *q;
//   cout<<endl;

//   for( q = m_pFirstNode ; q != NULL ; q = q->nextNode )
  //      cout<<endl<<q->data;

}

//returns the number of nodes in the linkedlist.  starting node is #1!!!
template<typename Type>
int LinkedList<Type>::count()
{
	//Iterating through this list isn't exactly blazing fast :/
   node *iteratingNode;
   int index=0;
   for( iteratingNode = m_pFirstNode; iteratingNode != NULL ; iteratingNode = iteratingNode->nextNode )
   {
        index++;
   }

   return index;
}

template<typename Type> 
LinkedList<Type>::~LinkedList()
{
   node *iteratingNode;
   if( m_pFirstNode == NULL )
        return;

   while( m_pFirstNode != NULL )
   {
      iteratingNode = m_pFirstNode->nextNode;
      delete m_pFirstNode;
      m_pFirstNode = iteratingNode;
   }
}



//DO NOT USE THIS FREQUENTLY WHEN NOT DEBUGGING!!!!  IT IS SLOW!
template<typename Type>
Type LinkedList<Type>::get(int nIndex)
{
	node *iteratingNode = m_pFirstNode;

	int iter = 0;
	while(iteratingNode != NULL && iter != nIndex)
	{
		iter++;
		iteratingNode = iteratingNode->nextNode;
	}

	if(iteratingNode == NULL)
	{
		MikeUtils::ASSERT(false, "Node not found in list!", __FILE__, __LINE__);
		//return NULL;
	}
	else if(iter == nIndex)
	{
		return iteratingNode->data;
	}

	//WTF!  Sanity check
	MikeUtils::ASSERT(false, "Node not found in list!", __FILE__, __LINE__);
	return m_pFirstNode->data;

}


#endif //LINKED_LIST_H